'''
@Problem description:
Given a string, find the length of the longest substring without repeating characters.
寻找字符串中最长连续子串使得子串不含有重复字符，返回子串长度。

@For example:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
'''


class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        length = 0
        maxLength = 0
        dic = {}
        for i in range(len(s)):
            if (s[i] not in dic.keys()):
                dic[s[i]] = i
                length += 1
            else:
                d = i - dic[s[i]]
                if (d <= length + 1):    #差值必须小于length+1，否则说明这个字符是上次重复字符更前面的字符
                    length = d
                else:
                    length += 1
                dic[s[i]] = i
            if (maxLength < length):
                maxLength = length
        return maxLength
